function Node(op, args) {
    this.op = op;
    this.args = args;
}

function isPowerExpression(str) {
    const regex = /^[a-zA-Z_][a-zA-Z0-9_]*\^(-|[-]?\d+|T)$/;
    return regex.test(str);
}

function extractNames(ast) {
    const names = [];

    function traverse(node) {
        if (node instanceof Node) {
            const op = node.op;
            const args = node.args;
            args.forEach(arg => traverse(arg));
        } else if (typeof node === 'string') {
            names.push(node);
        }
    }

    traverse(ast);

    return names;
}

function parseStringToAST(str) {
    const tokens = str.split('*');
    const ast = [];

    for (let i = 0; i < tokens.length; i++) {
        const token = tokens[i].trim();

        if (isPowerExpression(token)) {
            if (token.endsWith('^T')) {
                const base = token.substring(0, token.indexOf('^'));
                ast.push(new Node('transpose', [base]));
            } else if (token.endsWith('^-') || token.endsWith('^-1')) {
                const base = token.substring(0, token.indexOf('^'));
                ast.push(new Node('inverse', [base]));
            } else {
                const [base, exponent] = token.split('^');
                const e = parseInt(exponent);
                if (e < 0) {
                    ast.push(new Node('power', [new Node('inverse', [base]), -e]));
                } else {
                    ast.push(new Node('power', [base, e]));
                }
            }
        } else {
            ast.push(token);
        }
    }

    return ast.length === 1 ? ast[0] : new Node('multiply', ast);
}
